﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Boggle.TheGame
{
    /// <summary>
    /// This class contains methods used to run a merge sort on lists of objects
    /// Currently the only working implementation is a List of strings, which require
    /// their own method due to the flakey nature of strings and the way character equality works
    /// @author Zachary Behrmann
    /// </summary>
    static class MergeySort
    {
        /// <summary>
        /// Runs a merge sort on a List of Strings
        /// This specific sort is one that runs bottom up.
        /// By treating everything as one element and comparing it to the adjacent, 
        /// then moves up a power of 2, i.e. 1,2,4,8,16...
        /// </summary>
        /// <param name="toSort">The list of strings to sort</param>
        static public void MergeSort(List<String> toSort)
        {
            
            string[] working = toSort.ToArray(); //This is our working array
            int count = toSort.Count;
            for (int width = 1; width < count; width*= 2)
                //This loop defines what level of sorting we are on (powers of two)
            {
                for (int i = 0; i < count; i = i + (2 * width))
                    //This is where we sort the groups of strings
                {

                    int Left = i;
                    int Right = Math.Min(i + width, count);
                    int End = Math.Min( i+(2*width),count);

                    int LeftIncreasing = Left;
                    int RightIncreasing = Right;

                    for (int h = Left; h < End; h++)
                    {
                        if ((RightIncreasing >= End || string.Compare(toSort[LeftIncreasing], toSort[RightIncreasing], StringComparison.OrdinalIgnoreCase) <= 0) && LeftIncreasing < Right)
                            //If there is no more items to check on the right
                            //or the item on the left is less than or equal to the item on the right
                            //it is inserted into our working array next
                            //We must also make sure that the left item and the right item we are checking are not the same.
                        {
                            working[h] = toSort[LeftIncreasing];
                            
                            LeftIncreasing++; //Check the next item on the left
                        }
                        else
                            //otherwise the string we are comparing on the
                            //right is thrown in
                        {
                            working[h] = toSort[RightIncreasing];
                            RightIncreasing++; //Check the next item on the right
                        }
                    }
                }

                toSort.Clear(); //Clear the values of the list in order to
                toSort.AddRange(working); //reload the sorted values in order to begin the next level of sorting
            }
        }

        /// <summary>
        /// A generic implementation of merge sort,currently untested
        /// It would run the same as string merge sort, with the ommittance of
        /// the specializd "string.Compare"
        /// No test has been run because of a lack of need
        /// </summary>
        /// <typeparam name="T">The type stored in the list we are sorting</typeparam>
        /// <param name="toSort">The list to run merge sort on</param>
        static public void MergeSort<T>(List<T> toSort)
            where T : IComparable<T>
        {
            T[] working = toSort.ToArray(); //This is our working array
            int count = toSort.Count;
            for (int width = 1; width < count; width *= 2)
            //This loop defines what level of sorting we are on (powers of two)
            {
                for (int i = 0; i < count; i = i + (2 * width))
                //This is where we sort the groups of strings
                {

                    int Left = i;
                    int Right = Math.Min(i + width, count);
                    int End = Math.Min(i + (2 * width), count);

                    int LeftIncreasing = Left;
                    int RightIncreasing = Right;

                    for (int h = Left; h < End; h++)
                    {
                        if ((RightIncreasing >= End || toSort[LeftIncreasing].CompareTo(toSort[RightIncreasing]) <= 0) && LeftIncreasing < Right)
                        //If there is no more items to check on the right
                        //or the item on the left is less than or equal to the item on the right
                        //it is inserted into our working array next
                        //We must also make sure that the left item and the right item we are checking are not the same.
                        {
                            working[h] = toSort[LeftIncreasing];

                            LeftIncreasing++; //Check the next item on the left
                        }
                        else
                        //otherwise the string we are comparing on the
                        //right is thrown in
                        {
                            working[h] = toSort[RightIncreasing];
                            RightIncreasing++; //Check the next item on the right
                        }
                    }
                }

                toSort.Clear(); //Clear the values of the list in order to
                toSort.AddRange(working); //reload the sorted values in order to begin the next level of sorting
            }
        }


    }
}
